#include "headfiles.h"

//If tree1 contains all nodes in tree2, we consider tree1 contains tree2.
bool containBinaryTree(NODE *tree1, NODE *tree2) {
	if (tree2 == NULL) {
		return true;
	}

	// Tree1 is NULL and tree2 is NOT, return false;
	if (tree1 == NULL) {
		return false;
	}

	// If the head node does not have the same value, 
	// tree1 does not contain tree2
	if (tree1->i != tree2->i) {
		return false;
	}
	else {
		return (containBinaryTree(tree1->left, tree2->left) &&
			   containBinaryTree(tree1->right, tree2->right));
	}

	return true;
}

bool checkSubBinaryTree(NODE *head1, NODE *head2) {
	// Use each node of tree1 as the head and check whether 
	// the corresponding subtree contains head2
	if (containBinaryTree(head1, head2)) {
		return true;
	}
	else {
		if (head1 == NULL) {
			return false;
		}
		else {
			return (checkSubBinaryTree(head1->left, head2) ||
				   	checkSubBinaryTree(head1->right, head2));
		}
	}
}

